package myjava.i_collection;

/**
 * @Auther: cty
 * @Date: 2019/11/11 下午3:39
 * @Description: 自定义实现一个LinkedList
 * @version: 1.0
 */


public class E_MyLinkedList<E> {
    private Node first;
    private Node last;
    private int size;

    //在尾部增加一个节点
    public void add(E obj){
        Node node = new Node(obj);

        if(first==null){
            first = node;
            last = node;
        }else{
            last.next = node;  //将上一个节点next指向当前节点
            node.previous = last;  //将当前节点previous指向上一个节点
            node.next = null;  //将当前节点的next设置为空

            last = node;  //最后将last指向当前节点node
        }
        size++;
    }

    //toString转为字符串
    public String toString(){
        StringBuffer sb = new StringBuffer("[");
        Node temp = first;

        while (temp!=null){
            sb.append(temp.element+",");
            temp = temp.next;
        }
        sb.setCharAt(sb.length()-1,']');

        return sb.toString();
    }

    // 检查输入的索引是否合法
    public void checkRange(int index){
        if(index<0 || index>size-1){
            throw new RuntimeException("索引数字不合法："+index);
        }
    }

    //getNode——由传入的索引获取指定的节点
    public Node getNode(int index){
        checkRange(index);

        Node temp = null;
        if(index<=(size>>1)){  //小于总元素的一半，从头开始查询
            temp = first;
            for(int i=0;i<index;i++){
                temp = temp.next;
            }
        }else{  //否则，从尾部倒着查询
            temp = last;
            for(int i=size-1;i>index;i--){
                temp = temp.previous;
            }
        }
        return temp;
    }

    //get——由传入的索引获取指定的元素
    public E get(int index){
        checkRange(index);
        Node temp = getNode(index);
        return (E)temp.element;
        //return temp!=null?temp.element:null;  //我认为一定不为空
    }

    //remove——由传入的索引删除指定的节点
    public void remove(int index){
        checkRange(index);
        Node temp = getNode(index);  //先获取指定节点
        if(index==0){  //头节点的处理
            first = temp.next;
            first.previous = null;
        }else if(index==size-1){  //尾节点的处理
            last = temp.previous;
            last.next = null;
        }else {  //中间节点的处理
            Node up = temp.previous;
            Node down = temp.next;
            up.next = down;
            down.previous = up;
        }
        size--;
    }

    //add——由传入的索引在指定位置添加节点
    public void add(int index,E obj){
        checkRange(index);
        Node temp = getNode(index);  //先获取指定节点
        Node node = new Node(obj);

        if(index==0){  //头节点的处理
            first.previous = node;
            node.next = first;
            first = node;
        }else if(index==size-1){  //尾节点的处理
            last.next = node;
            node.previous = last;
            last = temp;
        }else {  //中间节点的处理
            Node up = temp;
            Node down = temp.next;

            down.previous = node;
            node.next = down;

            up.next = node;
            node.previous = up;
        }
        size++;
    }

    //主程序
    public static void main(String[] args) {
        E_MyLinkedList<String> list = new E_MyLinkedList<>();
        list.add("a");
        list.add("b");
        list.add("c");
        list.add("d");
        list.add("e");
        list.add("f");

        System.out.println(list);
        list.remove(3);
        System.out.println(list);
        list.remove(0);
        System.out.println(list);
        list.remove(3);
        System.out.println(list);
        list.add(0,"1");
        System.out.println(list);
        list.add(list.size-1,"2");
        System.out.println(list);
        list.add(3,"3");
        System.out.println(list);

        System.out.println(list.get(3));
    }
}


//Node节点类
class Node {
    Node previous;  //上一个节点
    Node next;  //下一个节点
    Object element;  //元素数据

    public Node(Node previous,Node next,Object element){
        super();
        this.previous = previous;
        this.next = next;
        this.element = element;
    }

    public Node(Object element) {
        super();
        this.element = element;
    }
}


